package main

var buffer []int

func merge(nums []int, left, right, mid int) {
	tmp := buffer[:0]
	i := left
	j := mid + 1
	for i <= mid && j <= right {
		if nums[i] < nums[j] {
			tmp = append(tmp, nums[i])
			i++
		} else {
			tmp = append(tmp, nums[j])
			j++
		}
	}
	if i <= mid {
		tmp = append(tmp, nums[i:mid+1]...)
	}
	if j <= right {
		tmp = append(tmp, nums[j:right+1]...)
	}
	copy(nums[left:right+1], tmp)
}

func msort(nums []int, left, right int) {
	if left >= right {
		return
	}
	mid := (left + right) / 2
	msort(nums, left, mid)
	msort(nums, mid + 1, right)
	merge(nums, left, right, mid)
}

func sortArray(nums []int) []int {
    msort(nums, 0, len(nums)-1)
	return nums
}

func main() {
	res := sortArray([]int{5, 2, 3, 1, 4})
	println(res)

	res = sortArray([]int{1, 1, 5, 7, 3})
	println(res)
}